package com.nika.usercenter.utils;

import java.util.Arrays;
import java.util.List;
import java.util.Objects;

public class AlgorithmUtils {
    public static void main(String[] args) {
        List<String> tag1 = Arrays.asList("Java","大一","男");
        List<String> tag2 = Arrays.asList("Java","大一","女","python","alsdas");
        double similar = levenshtein(tag1, tag2);
        System.out.println(similar);

    }

    /**
     * 匹配两组标签的相近程度
     * @param tag1
     * @param tag2
     * @author nika
     * @return
     */
    public static float levenshtein(List<String> tag1, List<String> tag2) {
        // 计算两个字符串的长度。
        int len1 = tag1.size();
        int len2 = tag2.size();
        // 建立上面说的数组，比字符长度大一个空间
        int[][] dif = new int[len1 + 1][len2 + 1];
        // 赋初值，步骤B。
        for (int a = 0; a <= len1; a++) {
            dif[a][0] = a;
        }
        for (int a = 0; a <= len2; a++) {
            dif[0][a] = a;
        }
        // 计算两个字符是否一样，计算左上的值
        int temp;
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (Objects.equals(tag1.get(i - 1), tag2.get(j - 1))) {
                    temp = 0;
                } else {
                    temp = 1;
                }
                // 取三个值中最小的
                dif[i][j] = min(dif[i - 1][j - 1] + temp, dif[i][j - 1] + 1, dif[i - 1][j] + 1);

            }
        }
        float similarity = 1 - (float) dif[len1][len2] / Math.max(tag1.size(), tag2.size());
        return similarity;
    }

    private static int min(int a, int b, int c) {
        int min = Math.min(a, b);
        return Math.min(min, c);
    }
}
